package com.study.algorithm;

/**
 * n皇后问题回溯法求解
 */
public class NQueen {

  private int n;
  private long count;
  private int[] arr;

  public NQueen(int n) {
    this.n = n;
    count = 0;
    arr = new int[n];
  }


  /**
   * row代表行 col代表列 假设row=5就会遍历0,1,2,3,4行
   * 假设8皇后问题那么就是8*8的正方形格子 arr[8] arr[0]=7代表第一行的皇后在第8列
   * 也就是arr[i]=j代表第i+1行的皇后在第j+1列
   *
   * @param row
   * @param col
   * @return
   */
  public boolean Check(int row, int col) {
    //遍历当前行之前的所有行
    for (int i = 0; i < row; ++i) {
      if (col == arr[i] || Math.abs(row - i) == Math.abs(col - arr[i])) //在同一列或者在同一斜线,一定不在同一行
      {
        return false;
      }
    }
    return true;
  }

  public void FindNQueen(int row) {
    if (row == n) {   //求出一种解, count+1
      count++;
      return;
    }

    for (int col = 0; col < n; ++col) {
      if (Check(row, col)) {   //检查是否满足条件
        arr[row] = col;      //记录
        FindNQueen(row + 1);   //递归查找
      }
    }

  }

  public static void main(String args[]) {
    NQueen nQueen = new NQueen(8);
    nQueen.FindNQueen(0);
    System.out.println(nQueen.count);
  }
}
